package Offer;

import java.util.Stack;

/**
 * 二叉搜索树的后序遍历序列
 * @author 是阿秋啊
 * @date 2022/04/18 21:34
 **/
public class Num33 {
    // 后序遍历加递归
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder,0,postorder.length - 1);
    }

    private boolean helper(int[] postorder, int l, int r) {
        if (l >= r) {
            return true;
        }
        int p = l;
        // 先找到当前根节点的右子树的第一个位置
        while (postorder[p] < postorder[r]) {
            p++;
        }
        int m = p;
        // 找到所有右子树范围
        while (postorder[p] > postorder[r]) {
            p++;
        }
        // 此时p一定走到当前根节点，因为在后序遍历中，根节点与右子树序列中不可能存在有比根节点小的数
        return p == r && helper(postorder,l,m - 1) && helper(postorder,m,r - 1);
    }
    // 方法二：单调栈
    public boolean verifyPostorder2(int[] postorder) {
        // 倒过来遍历，根右左
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1 ; i > 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}
